//	 ID : pallab81
// 	PROG : 10937
// 	LANG : C++
// 	2011-10-17-16.34.02 Monday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//


#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

inline void wait( double seconds ){
    double endtime = clock()+( seconds* CLOCKS_PER_SEC );
    while( clock() < endtime ){
        ;
    }
}

int h,w;
char G[52][52];
vector< pair<int,int> > treasure;
int dist[ 11 ][ 11 ];
int total_treasure;
inline void Read(){
    fo(i,h){
        fo(j,w){
            cin>>G[i][j];
        }
    }
    treasure.clear();
    fo(i,h){
        fo(j,w){
            if( G[i][j]=='@' ){
                treasure.pb( mk(i,j) );
                goto L1;
            }
        }
    }
L1:
    total_treasure=0;
    fo(i,h){
        fo(j,w){
            if( G[i][j]=='!' ){
                treasure.pb( mk(i,j) );
                ++total_treasure;
            }
        }
    }
}
int cost[52][52];
int r[] = {+0,+0,-1,+1, -1, -1, +1, +1};
int c[] = {-1,+1,+0,+0, -1, +1, +1, -1};
inline void bfs(int sr, int sc){
    fo(i,h){
        fo(j,w){
            cost[i][j] = (int)1023456789;
        }
    }
    queue< pair<int,int> > q;
    q.push( mk(sr,sc) );
    cost[sr][sc]=0;

    while( q.empty()==false ){

        int r_ = q.front().f;
        int c_ = q.front().s;
        assert(r_>=0 && r_<h);
        assert(c_>=0 && c_<w);
        q.pop();

        fo(i,4){
            int tr = r_+r[i];
            int tc = c_+c[i];
            if( tr<0 || tc<0 || tr>=h || tc>=w )continue;
            if( G[tr][tc]=='~')continue;
            if( G[tr][tc]=='#')continue;
            if( G[tr][tc]=='*')continue;

                bool fine=true;
                for(int j=0;j<8;++j){
                    int ttr = r_+r[j];
                    int ttc = c_+c[j];
                    if( ttr<0 || ttc<0 || ttr>=h || ttc>=w )continue;
                    if( G[ttr][ttc]=='*' ){
                        fine=false;
                    }
                }
                if( fine ){
                    int new_cost = cost[r_][c_]+1;
                    if( new_cost < cost[ tr][tc] ){
                        cost[tr][tc] = new_cost;
                        q.push( mk(tr,tc) );
                    }
                }
        }

    }
}
inline void calculateAll(){
    for(int i=0,j=SZ(treasure); i<j; ++i){
        int sr = treasure[i].f;
        int sc = treasure[i].s;
            bfs(sr,sc);
            for(int a=0;a<j;++a){
                dist[i][a] = cost[ treasure[a].f ][ treasure[a].s ];
            }
    }
}
inline bool isSeen(int mask, int id){
    return ( mask&(1<<id) ) ;
}
inline int Seen(int mask, int id){
    return ( mask|(1<<id) ) ;
}
int dp[11][ 1<<11 ];
inline int go(int id, int mask){
    if( __builtin_popcount(mask) == total_treasure ){
        return dist[id][0];
    }
    int& best = dp[id][ mask ];
    if( best!=-1 ){
        return best;
    }
    best = (int)1023456789;

        for(int i=0;i<total_treasure;++i){
                if( isSeen(mask,i)==false ){
                    int var = dist[id][i+1] + go( i+1, Seen(mask,i) );
                    best = min( best, var );
                }
        }

return best;
}
inline void Proc(){
    calculateAll();
    SET( dp,-1 );
    int var = go(0,0);
    cout<< (var<(int)1023456789 ? var : -1 ) <<"\n";
}

int main(){
	#ifndef ONLINE_JUDGE
		freopen("in","rt",stdin);
	#endif

        while( scanf("%d %d",&h,&w)==2 ){
            if( h==0 && w==0 ) break;
            Read();
            Proc();
        }


return 0;
}
